|
In mathematics, the Strahler number or Horton–Strahler number of a mathematical tree is a numerical measure of its branching complexity. These numbers were first developed in hydrology by and ; in this application, they are referred to as the Strahler stream order and are used to define stream size based on a hierarchy of tributaries. They also arise in the analysis of L-systems and of hierarchical biological structures such as (biological) trees and animal respiratory and circulatory systems, in register allocation for compilation of high-level programming languages and in the analysis of social networks. Alternative stream ordering systems have been developed by Shreve〔Shreve, R.L., 1966. Statistical law of stream numbers. Journal of Geology 74, 17–37.〕〔Shreve, R.L., 1967. Infinite topologically random channel networks. Journal of Geology 75, 178–186.〕 and Hodgkinson et al.〔Hodgkinson, J.H., McLoughlin, S. & Cox, M.E. 2006. The influence of structural grain on drainage in a metamorphic sub-catchment: Laceys Creek, southeast Queensland, Australia. Geomorphology, 81: 394-407.〕 ==Definition== All trees in this context are directed graphs, oriented from the root towards the leaves; in other words, they are arborescences. The degree of a node in a tree is just its number of children. One may assign a Strahler number to all nodes of a tree, in bottom-up order, as follows: *If the node is a leaf (has no children), its Strahler number is one. *If the node has one child with Strahler number ''i'', and all other children have Strahler numbers less than ''i'', then the Strahler number of the node is ''i'' again. *If the node has two or more children with Strahler number ''i'', and no children with greater number, then the Strahler number of the node is ''i'' + 1. The Strahler number of a tree is the number of its root node. Algorithmically, these numbers may be assigned by performing a depth-first search and assigning each node's number in postorder. The same numbers may also be generated via a pruning process in which the tree is simplified in a sequence of stages, where in each stage one removes all leaf nodes and all of the paths of degree-one nodes leading to leaves: the Strahler number of a node is the stage at which it would be removed by this process, and the Strahler number of a tree is the number of stages required to remove all of its nodes. Another equivalent definition of the Strahler number of a tree is that it is the height of the largest complete binary tree that can be homeomorphically embedded into the given tree; the Strahler number of a node in a tree is similarly the height of the largest complete binary tree that can be embedded below that node. Any node with Strahler number ''i'' must have at least two descendants with Strahler number ''i'' − 1, at least four descendants with Strahler number ''i'' − 2, etc., and at least 2''i'' − 1 leaf descendants. Therefore, in a tree with ''n'' nodes, the largest possible Strahler number is log2 ''n'' + 1. However, unless the tree forms a complete binary tree its Strahler number will be less than this bound. In an ''n''-node binary tree, chosen uniformly at random among all possible binary trees, the expected index of the root is with high probability very close to log4 ''n''.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Strahler number」の詳細全文を読む スポンサード リンク
|